package com.zyj.test.month1.day5;

import java.util.ArrayList;
import java.util.List;

/**
 * @author Yijia Zhang
 * @create 2024-04-26 23:34
 */
public class code1146 {
    static class SnapshotArray {
        int idx;
        List<List<int[]>> arr;

        public SnapshotArray(int length) {
            this.idx = 0;
            this.arr = new ArrayList<>(length);
            for (int i = 0; i < length; i++) {
                ArrayList<int[]> list = new ArrayList<>();
                list.add(new int[2]);
                this.arr.add(list);
            }

        }

        public void set(int index, int val) {
            List<int[]> arrIndex = arr.get(index);
            int[] lastIdx = arrIndex.get(arrIndex.size() - 1);
            if (lastIdx[0] < idx) {
                arrIndex.add(new int[] {idx, val});
            } else {
                lastIdx[1] = val;
            }

        }

        public int snap() {
            return idx++;
        }

        public int get(int index, int snap_id) {
            List<int[]> goal = arr.get(index);
            //二分
            int l = 0, r = goal.size() - 1;
            while (l < r) {
                int mid = l + (r - l + 1 >> 1);
                int now = goal.get(mid)[0];
                if (now <= snap_id) {
                    l = mid;
                } else {
                    r = mid - 1;
                }
            }
            return goal.get(l)[1];
        }
    }
}
